Traceability of line graphs

Brualdi and Shanny [R.A. Brualdi, R.F. Shanny, Hamiltonian line graphs, J. Graph Theory 5 (1981) 307-314], Clark [L. Clark, On hamitonian line graphs, J. Graph Theory 8 (1984) 303-307] and Veldman [H.J. Veldman, On dominating and spanning circuits in graphs, Discrete Math. 124 (1994) 229-239] gave minimum degree conditions of a line graph guaranteeing the line graph to be hamiltonian. In this paper, we investigate the similar conditions guaranteeing a line graph to be traceable. In particular, we show the following result: let G be a simple graph of order n and L(G) its line graph. If n is sufficiently large and, either ; or and G is almost bridgeless, then L(G) is traceable. As a byproduct, we also show that every 2-edge-connected triangle-free simple graph with order at most 9 has a spanning trail. These results are all best possible.     

On spanning tree congestion of graphs

Let G be a connected graph and T be a spanning tree of G. For e∈E(T), the congestion of e is the number of edges in G connecting two components of T−e. The edge congestion ofGinT is the maximum congestion over all edges in T. The spanning tree congestion ofG is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes.     

On the spanning fan-connectivity of graphs

Let G be a graph. The connectivity of G, κ(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, C_k(u,v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k^∗-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, κ^∗(G), is the maximum integer k such that G is w^∗-connected for 1≤w≤k if G is 1^∗-connected.Let x be a vertex in G and let U={y₁,y₂,…,y_k} be a subset of V(G) where x is not in U. A spanningk−(x,U)-fan, F_k(x,U), is a set of internally-disjoint paths {P₁,P₂,…,P_k} such that P_i is a path connecting x to y_i for 1≤i≤k and . A graph G is k^∗-fan-connected (or -connected) if there exists a spanning F_k(x,U)-fan for every choice of x and U with |U|=k and x∉U. The spanning fan-connectivity of a graph G, , is defined as the largest integer k such that G is -connected for 1≤w≤k if G is -connected.In this paper, some relationship between κ(G), κ^∗(G), and are discussed. Moreover, some sufficient conditions for a graph to be -connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k^∗-pipeline-connected.     

Small subsets of groups

Given an infinite group G and an infinite cardinal κ|G|, we say that a subset A of G is κ-large (κ-small) if there exists F[G]^<κ such that G=FA (GFA is κ-large for each F[G]^<κ). The subject of the paper is the family of all κ-small subsets. We describe the left ideal of the right topological semigroup βG determined by . We study interrelations between κ-small and other (P_κ-small and κ-thin) subsets of groups, and prove that G can be generated by some 2-thin subsets. We partition G in countable many subsets which are κ-small for each κω. We show that [G]^<κ is dual to provided that either κ is regular and κ=|G|, or G is Abelian and κ is a limit cardinal, or G is a divisible Abelian group.     

Remarks on the lattices of fuzzy subsets of a groupoid

In this paper we give a necessary and sufficient condition for a groupoid D such that the sup-min product is distributive over arbitrary intersection of fuzzy subsets of D, and correct some results from the paper [S. Ray, The lattice of all idempotent fuzzy subsets of a groupoid, Fuzzy Sets and Systems 96 (1998) 239–245]. Also, we prove that the set of all idempotent fuzzy sets forms a complete lattice, which is a complete join-sublattice of the lattice of all fuzzy subgroupoids. This result extends the corresponding result from the above mentioned paper.     

A new construction of vertex algebras and quasi-modules for vertex algebras

In this paper, a new construction of vertex algebras from more general vertex operators is given and a notion of quasimodule for vertex algebras is introduced and studied. More specifically, a notion of quasilocal subset(space) of for any vector space W is introduced and studied, generalizing the notion of usual locality in the most possible way, and it is proved that on any maximal quasilocal subspace there exists a natural vertex algebra structure and that any quasilocal subset of generates a vertex algebra. Furthermore, it is proved that W is a quasimodule for each of the vertex algebras generated by quasilocal subsets of . A notion of Γ-vertex algebra is also introduced and studied, where Γ is a subgroup of the multiplicative group C^× of nonzero complex numbers. It is proved that any maximal quasilocal subspace of is naturally a Γ-vertex algebra and that any quasilocal subset of generates a Γ-vertex algebra. It is also proved that a Γ-vertex algebra exactly amounts to a vertex algebra equipped with a Γ-module structure which satisfies a certain compatibility condition. Finally, two families of examples are given, involving twisted affine Lie algebras and certain quantum torus Lie algebras.     

Stable routing under the Spanning Tree Protocol

The Spanning Tree Protocol routes traffic on shortest path trees. If some edges fail, the traffic has to be rerouted consequently, setting up alternative trees. In this paper we design efficient algorithms to compute polynomial-size integer weights so as to enforce the following stability property: if q=O(1) edges fail, traffic demands that are not affected by the failures are not redirected. Stability is a goal pursued by network operators in order to minimize transmission delays due to the restoration process.     

A condition for assured 3-face-colorability of infinite plane graphs with a given spanning tree

Given an infinite leafless tree drawn on the plane, we ask whether or not one can add edges between the vertices of the tree obtaining a non-3-face-colorable graph. We formulate a condition conjectured to be necessary and sufficient for this to be possible. We prove that this condition is indeed necessary and sufficient for trees with maximal degree 3, and that it is sufficient for general trees. In particular, we prove that every infinite plane graph with a spanning binary tree is 3-face-colorable.     

Spanning Euler tours and spanning Euler families in hypergraphs with particular vertex cuts

An Euler tour in a hypergraph is a closed walk that traverses each edge of the hypergraph exactly once, while an Euler family, first defined by Bahmanian and ?ajna, is a family of closed walks that jointly traverse each edge exactly once and cannot be concatenated. In this paper, we study the notions of a spanning Euler tour and a spanning Euler family, that is, an Euler tour (family) that also traverses each vertex of the hypergraph at least once. We examine necessary and sufficient conditions for a hypergraph to admit a spanning Euler family, most notably when the hypergraph possesses a vertex cut consisting of vertices of degree two. Moreover, we characterise hypergraphs with a vertex cut of cardinality at most two that admit a spanning Euler tour (family). This result enables us to reduce the problem of existence of a spanning Euler tour (which is NP-complete), as well as the problem of a spanning Euler family, to smaller hypergraphs.     

基于可减的实半环与实素理想

半环R被称为实半环,若对于任意的n∈N,方程x1^2＋…＋xn^2=0在R中只有零解：x1=…=xn=0.为了刻画实半环,引入了实理想和极小素理想的概念,利用同余的方法,得到了可减半环类中实半环的结构定理.